"""
希尔排序
希尔排序是插⼊排序的⼀種更⾼效的改进版本，通过初始使⽤⼤间隔的插⼊排序来减少数据量。
"""

"""
def shell_sort(arr):
    n = len(arr)  # 获取数组长度
    gap = n // 2  # 初始化间隔为数组长度的一半

    while gap > 0:  # 当间隔大于0时继续循环
        for i in range(gap, n):  # 从间隔位置开始遍历数组
            temp = arr[i]  # 将当前元素存储到临时变量中
            j = i  # 初始化索引j为当前位置i
            # 比较并移动元素，直到找到合适的位置插入
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]  # 将前面的元素后移
                j -= gap  # 向前移动索引j
            arr[j] = temp  # 将临时变量中的值插入到正确位置
        gap //= 2  # 缩小间隔，继续下一轮排序
"""

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap,n):
            temp = arr[i]
            j = i
            while j > gap and arr[j-gap] > temp:
                arr[i] = arr[j-gap]
                j-=gap
            arr[j] =temp
        gap//=2


# 示例用法
arr = [12, 34, 54, 2, 3]
shell_sort(arr)
print("排序后:", arr)  # 输出排序后的数组